1383. Maximum Performance of a Team
Hard

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

 

Constraints:

  • 1 <= k <= n <= 105
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 105
  • 1 <= efficiency[i] <= 108
Accepted
32.2K
Submissions
78.1K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Keep track of the engineers by their efficiency in decreasing order.
Show Hint 2
Starting from one engineer, to build a team, it suffices to bring K-1 more engineers who have higher efficiencies as well as high speeds.

Average Rating: 4.85 (46 votes)

Premium

Solution


Overview

At first glance, the problem might seem to be a combination problem (e.g. Combination Sum III), meaning one could enumerate all possible compositions and return the team with the maximum performance based on the given benchmark.

However, while this brute force idea is intuitive, it is also inefficient, because the number of combinations grows exponentially with the number of engineers. In fact, there are some insights that can be derived from the problem, which we can leverage to greatly speed up the algorithm.

In this article, we will introduce a greedy algorithm together with the application of priority queue to solve the problem.


Approach: Greedy with Priority Queue

Intuition

As a reminder, the performance of a team is defined as the sum of all members' speeds multiplied by the minimum efficiency among the members.

As one can see, the performance of a team depends on two variables.

To facilitate the enumeration process, let us first fix the value of one of the variables, namely the minimum efficiency of the team.

The key idea behind the enumeration process is as follows:

For each candidate, we treat him/her as the one who has the minimum efficiency in a team. Then, we select the rest of the team members based on this condition.

  • The above enumeration is sound, which means it is guaranteed to find the optimal solution to the problem. For example, before arriving at a final solution where candidate X has the minimum efficiency on the team, we must have enumerated all potential team compositions that include candidate X.

  • Most importantly, the above enumeration helps prune some of the unnecessary team compositions. Hence it runs significantly faster. Starting from a fixed candidate and only accepting new team members that have a higher efficiency than the fixed candidate, allows us to only consider teams of size k, rather than enumerating all teams of size one to k. This is because once the minimum efficiency of a team is fixed, each new team member is guaranteed to improve the team's performance. Therefore, we should add as many new members as possible.

Actually, the above enumeration can be categorized as a Greedy algorithm, where we decompose a problem into a series of stages, and at each stage we make the locally optimal choice.

In our case, we derive the solution through an enumeration process, where at each step we build a locally optimal team by starting from a fixed engineer with the minimum efficiency on the team. At the end of the enumeration process, we select the maximum among the locally optimal solutions to obtain the globally optimal solution.

Algorithm

To see how the above enumeration works, let us walk through some concrete examples.

Suppose that we have a list of 6 engineers with speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], and we are asked to compose a team with at most k=2 members.

Here are three steps that demonstrate how we can compose a team with the maximum performance and with at most k members.

1). Let's select the first engineer from the list of candidates as a potential member of the team. The first engineer has speed of 2 and an efficiency of 5.

More importantly, we will impose a condition that all future team members must have an efficiency greater than or equal to the first team member.

example step 1

2). Next, we will select the rest of the team members. We will use the following criteria in order to maximize the performance of the team:

  • Each of the selected members should have an efficiency that is at least as high as the engineer that was picked in the first step.

  • With the minimum effiency fixed, it will be beneficial to pick as many additional members as possible, up to the maximum quota of k-1 members.

With the first candidate fixed as a member of the team, we need to select at most one more member for the team. We are limited to at most one more member because k-1 = 2-1 = 1.

example step 2

According to the criteria listed above, in order to maximize the performance of the team, we should invite the fifth candidate to join the team. Here is the rationale. Both the fourth and fifth candidates have a higher efficiency than the first candidate. Therefore, both of them are eligible to join the team. However, since the fifth candidate is faster than the fourth candidate, it is optimal to choose the fifth candidate in order to maximize the total speed of the team, and therefore maximize the performance of the team.

3). We repeat the above two steps for each of the remaining candidates. At the end of the enumeration process, we will discover that the team composition with the second candidate as the one with the minimum efficiency will emerge as the one with the maximum performance.

example step 3

Implementation

The most complex step in the algorithm is the second step. In the second step, we have selected a member who will have the lowest efficiency in the team, and we must determine how to construct the rest of the team. We can answer this question, by breaking it down into two tasks:

  • First of all, given a fixed member, we must find all eligible candidates (at most k-1 members) whose efficiencies are higher than the fixed member's efficiency.

    • To achieve this task, we could sort the candidates, in descending order, based on efficiency.

    • We then iterate through the sorted candidates. For each candidate, we only need to consider the earlier candidates. Since the list is sorted, only the earlier candidates will have a higher efficiency than the current candidate.

  • Given all the eligible candidates, in order to maximize the total speed, we need to find the fastest k-1 eligible candidates.

    • To achieve this task, we can sort the candidates again. But this time, we sort only the earlier candidates, and most importantly we sort by speed rather than efficiency.

    • The sorting idea is a valid one. However, a more efficient option would be to apply the Priority Queue data structure here. The priority queue, also known as heap, is a data structure which dynamically maintains the order of elements based on some predefined priority. The priority queue is well-known for its optimized time complexity when maintaining a list of sorted elements. As such, we will we opt to use a priority queue in the following implementation.

algorithm

To recap, we will build a greedy algorithm that utilizes the priority queue data structure. Here are the steps in detail.

  • First of all, let's sort the candidates by efficiency in descending order.

  • Then, we will iterate through the sorted candidates.

    • At each iteration, our goal is to construct a team with at most k members, while treating the current candidate as the one with the lowest efficiency on the team.
    • We use a priority queue to store the speeds for the rest k-1 team members. The priority queue is maintained as a sliding window along with our iteration. For example, we pop out the member with the lowest speed when we exceed the predefined capacity of the queue, which is k-1.

Complexity Analysis

Let NN be the total number of candidates, and KK be the size of the team.

  • Time Complexity: O(N(logN+logK))O\big(N \cdot (\log N + \log K)\big)

    • First of all, we build a list of candidates from the inputs, which takes O(N)O(N) time.

    • We then sort the candidates, which takes O(NlogN)O(N \log N) time.

    • We iterate through the sorted candidates. At each iteration, we will perform at most two operations on the priority queue: one push and one pop. Each operation takes O(log(K1))O\big(\log (K-1) \big) time, where K1K-1 is the capacity of the queue. To sum up, the time complexity of this iteration will be O(Nlog(K1))=O(NlogK)O\big(N \cdot \log (K-1)\big) = O(N \cdot \log K).

    • Thus, the overall time complexity of the algorithm will be O(N(logN+logK))O\big(N \cdot (\log N + \log K)\big).

  • Space Complexity: O(N+K)O(N + K)

    • We build a list of candidates from the inputs, which takes O(N)O(N) space.

    • We also use the priority queue data structure whose space capacity is O(K1)O(K-1).

    • Note that we use sorting in the algorithm, and the space complexity of the sorting algorithm depends on the implementation of each programming language. For instance, the sorted() function in Python is implemented with the Timsort algorithm whose space complexity is O(N)\mathcal{O}(N). While in Java, the Collections.sort() is implemented as a variant of the quicksort algorithm whose space complexity is O(logN)\mathcal{O}(\log{N}).

    • To sum up, the overall space complexity of the entire algorithm is O(N+K)O(N + K).


Report Article Issue

Comments: 6
_aaRPee_'s avatar
Read More

Although the Time complexity is totally correct, I was just curious if we can call it to be having a Time complexity of O(N log N), since K is never greater than N ??

8
Show 1 reply
Reply
Share
Report
vincentFeng0101's avatar
Read More

great problem and solution. This is a "hard" one but not that difficult once you see the idea behind it. test the basic things

4
Reply
Share
Report
flash_solve's avatar
Read More

Nice article, questions is more of just sailing through, than a really Tricky hard problem. I would prefer this question in an interview, over some really hard tricky problems out there, where if you don't know the trick, you're rejected.

8
Show 1 reply
Reply
Share
Report
Master-Oogway's avatar
Read More

Shouldn't there be an if() condition to check if the heap is full before calculating max perf at line 28 of the solution?
For example:
Input: 3
[2,8,2]
[2,7,1]
2

For the above input based on the examples given in the question, I would expect the answer to be 20. i.e., sum of first 2 entries (10+2) multiplies by min(2,7) which equals 20. However, based on the solution I would get the answer to be 56, which is wrong given the question description and the examples.
[Update]: Got the answer to my confusion. In the question its mentioned atmost k, so any max solution upto k should be considered. Thats the reason why the if condition was not there.

1
Reply
Share
Report
user3446TH's avatar
Read More

will O(n2) dp approach work?

0
Reply
Share
Report
anonymous1127's avatar
Read More

It's sailing more to medium problem than hard problem.

-28
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/05/2021 19:03Accepted116 ms36.8 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium